home *** CD-ROM | disk | FTP | other *** search
/ Mac Format 1995 June / MacFormat 25.iso / Shareware City / Developers / OutOfPhase1.1 Source / OutOfPhase Folder / Fractions.c < prev    next >
Text File  |  1994-08-15  |  14KB  |  353 lines
  1. /* Fractions.c */
  2. /*****************************************************************************/
  3. /*                                                                           */
  4. /*    Out Of Phase:  Digital Music Synthesis on General Purpose Computers    */
  5. /*    Copyright (C) 1994  Thomas R. Lawrence                                 */
  6. /*                                                                           */
  7. /*    This program is free software; you can redistribute it and/or modify   */
  8. /*    it under the terms of the GNU General Public License as published by   */
  9. /*    the Free Software Foundation; either version 2 of the License, or      */
  10. /*    (at your option) any later version.                                    */
  11. /*                                                                           */
  12. /*    This program is distributed in the hope that it will be useful,        */
  13. /*    but WITHOUT ANY WARRANTY; without even the implied warranty of         */
  14. /*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          */
  15. /*    GNU General Public License for more details.                           */
  16. /*                                                                           */
  17. /*    You should have received a copy of the GNU General Public License      */
  18. /*    along with this program; if not, write to the Free Software            */
  19. /*    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.              */
  20. /*                                                                           */
  21. /*    Thomas R. Lawrence can be reached at tomlaw@world.std.com.             */
  22. /*                                                                           */
  23. /*****************************************************************************/
  24.  
  25. #include "MiscInfo.h"
  26. #include "Audit.h"
  27. #include "Debug.h"
  28. #include "Definitions.h"
  29.  
  30. #include "Fractions.h"
  31. #include "Factoring.h"
  32.  
  33.  
  34. /* note: this module does NOT deal with negative numbers!!! */
  35.  
  36.  
  37. /* convert a decimal number to a fraction with the specified denominator limit */
  38. void                                Double2Fraction(double Value, unsigned long Denominator,
  39.                                             FractionRec* Fraction)
  40.     {
  41.         ERROR(Value < 0,PRERR(ForceAbort,"Double2Fraction:  value is less than zero"));
  42.         Fraction->Denominator = Denominator;
  43.         Fraction->Integer = Value;
  44.         Fraction->Fraction = (Value - Fraction->Integer) * Denominator + 0.5;
  45.         ReduceFraction(Fraction);
  46.     }
  47.  
  48.  
  49. /* convert fraction to a double */
  50. double                            Fraction2Double(FractionRec* Fraction)
  51.     {
  52.         ERROR(Fraction->Fraction >= Fraction->Denominator,PRERR(ForceAbort,
  53.             "Fraction2Double:  numerator is larger than denominator"));
  54.         return Fraction->Integer + ((double)Fraction->Fraction / Fraction->Denominator);
  55.     }
  56.  
  57.  
  58. /* add fractions.  Destination fraction can be one of the source fractions */
  59. void                                AddFractions(FractionRec* Left, FractionRec* Right, FractionRec* Dest)
  60.     {
  61.         unsigned long            FractionTemp;
  62.         unsigned long            DenominatorTemp;
  63.         unsigned long            IntegerTemp;
  64.  
  65.         ERROR(Left->Fraction >= Left->Denominator,PRERR(ForceAbort,
  66.             "AddFractions:  numerator is larger than denominator"));
  67.         ERROR(Right->Fraction >= Right->Denominator,PRERR(ForceAbort,
  68.             "AddFractions:  numerator is larger than denominator"));
  69.         /* add fractional parts */
  70. #if !DEBUG
  71.         if (Left->Denominator == Right->Denominator)
  72.             {
  73.                 /* if the denominators are the same, then adding is really easy */
  74.                 DenominatorTemp = Left->Denominator;
  75.                 FractionTemp = Left->Fraction + Right->Fraction;
  76.             }
  77.          else
  78. #endif
  79.             {
  80.                 unsigned long            GCF;
  81.  
  82.                 /* if the denominators are not the same, then we need to multiply each */
  83.                 /* side by some number so that they will be the same.  finding the greatest */
  84.                 /* common factor helps us find the smallest number to multiply by. */
  85.                 /* Left->Denominator / GCF = the factors that left has which right needs. */
  86.                 /* Right->Denominator / GCF = the factors that right has which left needs. */
  87.                 GCF = FindCommonFactors(Left->Denominator,Right->Denominator);
  88.                 /* by multiplying the denominators together, then dividing out the extra */
  89.                 /* set of common factors, we find the smallest common denominator.  The */
  90.                 /* division is performed inside to prevent overflow */
  91.                 DenominatorTemp = (Left->Denominator / GCF) * Right->Denominator;
  92.                 /* the left and right sides should yield the same denominator */
  93.                 ERROR(DenominatorTemp != (Right->Denominator / GCF) * Left->Denominator,
  94.                     PRERR(ForceAbort,"AddFractions:  couldn't factor denominators"));
  95.                 /* since we are multiplying each fraction by N/N, we need to multiply */
  96.                 /* the numerators by the same thing we multiplied the denominators by. */
  97.                 FractionTemp = Left->Fraction * (Right->Denominator / GCF)
  98.                     + Right->Fraction * (Left->Denominator / GCF);
  99.             }
  100.         /* add the integer components */
  101.         IntegerTemp = Left->Integer + Right->Integer;
  102.         /* if there was an overflow in the fractional part, carry it to the integer */
  103.         if (FractionTemp >= DenominatorTemp)
  104.             {
  105.                 /* since we are adding, the amount of carry should never be more than 1 */
  106.                 FractionTemp -= DenominatorTemp;
  107.                 IntegerTemp += 1;
  108.             }
  109.         ERROR(FractionTemp >= DenominatorTemp,PRERR(ForceAbort,
  110.             "AddFractions:  numerator is larger than denominator after reduction"));
  111.         /* store result */
  112.         Dest->Integer = IntegerTemp;
  113.         Dest->Fraction = FractionTemp;
  114.         Dest->Denominator = DenominatorTemp;
  115.     }
  116.  
  117.  
  118. /* test to see if the left is greater than the right */
  119. MyBoolean                        FracGreaterThan(FractionRec* Left, FractionRec* Right)
  120.     {
  121.         ERROR(Left->Fraction >= Left->Denominator,PRERR(ForceAbort,
  122.             "FracGreaterThan:  numerator is larger than denominator"));
  123.         ERROR(Right->Fraction >= Right->Denominator,PRERR(ForceAbort,
  124.             "FracGreaterThan:  numerator is larger than denominator"));
  125.         if (Left->Integer > Right->Integer)
  126.             {
  127.                 /* if the integer portion is bigger, then there's no contest */
  128.                 return True;
  129.             }
  130.         else if (Left->Integer < Right->Integer)
  131.             {
  132.                 /* same as above */
  133.                 return False;
  134.             }
  135.         else
  136.             {
  137.                 /* if the integer portions are the same, then we have to compare the */
  138.                 /* fractional portions */
  139. #if !DEBUG
  140.                 if (Left->Denominator == Right->Denominator)
  141.                     {
  142.                         /* if the denominators are the same, then comparison is easy */
  143.                         return Left->Fraction > Right->Fraction;
  144.                     }
  145.                  else
  146. #endif
  147.                     {
  148.                         unsigned long            GCF;
  149.  
  150.                         /* if the denominators are not the same, then they have to be */
  151.                         /* made the same.  as before, the GCF is the factors that are */
  152.                         /* common to both sides.  Left->Denominator / GCF is the portion of */
  153.                         /* the left that right needs and Right->Denominator / GCF is the portion */
  154.                         /* of the right that left needs.  We don't care about the new */
  155.                         /* denominator, but we will compare the new numerators. */
  156.                         GCF = FindCommonFactors(Left->Denominator,Right->Denominator);
  157.                         return Left->Fraction * (Right->Denominator / GCF)
  158.                             > Right->Fraction * (Left->Denominator / GCF);
  159.                     }
  160.             }
  161.     }
  162.  
  163.  
  164. /* test to see if the left is greater than or equal to the right */
  165. MyBoolean                        FracGreaterEqual(FractionRec* Left, FractionRec* Right)
  166.     {
  167.         ERROR(Left->Fraction >= Left->Denominator,PRERR(ForceAbort,
  168.             "FracGreaterThan:  numerator is larger than denominator"));
  169.         ERROR(Right->Fraction >= Right->Denominator,PRERR(ForceAbort,
  170.             "FracGreaterThan:  numerator is larger than denominator"));
  171.         if (Left->Integer > Right->Integer)
  172.             {
  173.                 /* if the integer portion is bigger, then there's no contest */
  174.                 return True;
  175.             }
  176.         else if (Left->Integer < Right->Integer)
  177.             {
  178.                 /* same as above */
  179.                 return False;
  180.             }
  181.         else
  182.             {
  183.                 /* if the integer portions are the same, then we have to compare the */
  184.                 /* fractional portions */
  185. #if !DEBUG
  186.                 if (Left->Denominator == Right->Denominator)
  187.                     {
  188.                         /* if the denominators are the same, then comparison is easy */
  189.                         return Left->Fraction >= Right->Fraction;
  190.                     }
  191.                  else
  192. #endif
  193.                     {
  194.                         unsigned long            GCF;
  195.  
  196.                         /* if the denominators are not the same, then they have to be */
  197.                         /* made the same.  as before, the GCF is the factors that are */
  198.                         /* common to both sides.  Left->Denominator / GCF is the portion of */
  199.                         /* the left that right needs and Right->Denominator / GCF is the portion */
  200.                         /* of the right that left needs.  We don't care about the new */
  201.                         /* denominator, but we will compare the new numerators. */
  202.                         GCF = FindCommonFactors(Left->Denominator,Right->Denominator);
  203.                         return Left->Fraction * (Right->Denominator / GCF)
  204.                             >= Right->Fraction * (Left->Denominator / GCF);
  205.                     }
  206.             }
  207.     }
  208.  
  209.  
  210. /* test fractions for equality */
  211. MyBoolean                        FractionsEqual(FractionRec* Left, FractionRec* Right)
  212.     {
  213.         ERROR(Left->Fraction >= Left->Denominator,PRERR(ForceAbort,
  214.             "FractionsEqual:  numerator is larger than denominator"));
  215.         ERROR(Right->Fraction >= Right->Denominator,PRERR(ForceAbort,
  216.             "FractionsEqual:  numerator is larger than denominator"));
  217.         if (Left->Integer != Right->Integer)
  218.             {
  219.                 /* if the integers aren't equal, then it's easy */
  220.                 return False;
  221.             }
  222.         else
  223.             {
  224. #if !DEBUG
  225.                 /* if the integer portions are the same, then we have to compare the */
  226.                 /* fractional portions */
  227.                 if (Left->Denominator == Right->Denominator)
  228.                     {
  229.                         /* if the denominators are the same, then comparison is easy */
  230.                         return Left->Fraction == Right->Fraction;
  231.                     }
  232.                  else
  233. #endif
  234.                     {
  235.                         unsigned long            GCF;
  236.  
  237.                         /* if the denominators are not the same, then they have to be */
  238.                         /* made the same.  as before, the GCF is the factors that are */
  239.                         /* common to both sides.  Left->Denominator / GCF is the portion of */
  240.                         /* the left that right needs and Right->Denominator / GCF is the portion */
  241.                         /* of the right that left needs.  We don't care about the new */
  242.                         /* denominator, but we will compare the new numerators. */
  243.                         GCF = FindCommonFactors(Left->Denominator,Right->Denominator);
  244.                         return Left->Fraction * (Right->Denominator / GCF)
  245.                             == Right->Fraction * (Left->Denominator / GCF);
  246.                     }
  247.             }
  248.     }
  249.  
  250.  
  251. /* reduce fraction */
  252. void                                ReduceFraction(FractionRec* Frac)
  253.     {
  254.         unsigned long            GCF;
  255.  
  256.         ERROR(Frac->Fraction >= Frac->Denominator,PRERR(ForceAbort,
  257.             "ReduceFraction:  numerator is larger than denominator"));
  258.         GCF = FindCommonFactors(Frac->Fraction,Frac->Denominator);
  259.         Frac->Fraction = Frac->Fraction / GCF;
  260.         Frac->Denominator = Frac->Denominator / GCF;
  261.     }
  262.  
  263.  
  264. /* multiply fractions.  destination can be one of the sources */
  265. /* this function will fail on numbers considerably smaller than the */
  266. /* range of representable fractions. */
  267. void                                MultFractions(FractionRec* Left, FractionRec* Right, FractionRec* Dest)
  268.     {
  269.         unsigned long            Numerator;
  270.         unsigned long            Denominator;
  271.  
  272.         ERROR(Left->Fraction >= Left->Denominator,PRERR(ForceAbort,
  273.             "MultFractions:  numerator is larger than denominator"));
  274.         ERROR(Right->Fraction >= Right->Denominator,PRERR(ForceAbort,
  275.             "MultFractions:  numerator is larger than denominator"));
  276.         /* the product of two fractions: A/B * C/D == AC/BD */
  277.         /* here we multiply the denominators */
  278.         Denominator = Left->Denominator * Right->Denominator;
  279.         /* here we multiply the numerators and convert the integer parts into */
  280.         /* part of the numerator */
  281.         Numerator = (Left->Integer + Right->Integer) * Denominator
  282.             + Left->Fraction * Right->Denominator
  283.             + Right->Fraction * Left->Denominator;
  284.         /* division gives us the integer part back and the remainder is the numerator */
  285.         Dest->Integer = Numerator / Denominator;
  286.         Dest->Fraction = Numerator % Denominator;
  287.         Dest->Denominator = Denominator;
  288.         /* since we multiplied, reduce so that denominators don't get out of hand */
  289.         ReduceFraction(Dest);
  290.     }
  291.  
  292.  
  293. /* subtract second fraction from first.  Destination can be one of the sources */
  294. void                                SubFractions(FractionRec* Left, FractionRec* Right, FractionRec* Dest)
  295.     {
  296.         long                            FractionTemp;
  297.         long                            DenominatorTemp;
  298.         long                            IntegerTemp;
  299.  
  300.         ERROR(Left->Fraction >= Left->Denominator,PRERR(ForceAbort,
  301.             "AddFractions:  numerator is larger than denominator"));
  302.         ERROR(Right->Fraction >= Right->Denominator,PRERR(ForceAbort,
  303.             "AddFractions:  numerator is larger than denominator"));
  304.         /* add fractional parts */
  305. #if !DEBUG
  306.         if (Left->Denominator == Right->Denominator)
  307.             {
  308.                 /* if the denominators are the same, then adding is really easy */
  309.                 DenominatorTemp = Left->Denominator;
  310.                 FractionTemp = Left->Fraction - Right->Fraction;
  311.             }
  312.          else
  313. #endif
  314.             {
  315.                 unsigned long            GCF;
  316.  
  317.                 /* if the denominators are not the same, then we need to multiply each */
  318.                 /* side by some number so that they will be the same.  finding the greatest */
  319.                 /* common factor helps us find the smallest number to multiply by. */
  320.                 /* Left->Denominator / GCF = the factors that left has which right needs. */
  321.                 /* Right->Denominator / GCF = the factors that right has which left needs. */
  322.                 GCF = FindCommonFactors(Left->Denominator,Right->Denominator);
  323.                 /* by multiplying the denominators together, then dividing out the extra */
  324.                 /* set of common factors, we find the smallest common denominator.  The */
  325.                 /* division is performed inside to prevent overflow */
  326.                 DenominatorTemp = (Left->Denominator / GCF) * Right->Denominator;
  327.                 /* the left and right sides should yield the same denominator */
  328.                 ERROR(DenominatorTemp != (Right->Denominator / GCF) * Left->Denominator,
  329.                     PRERR(ForceAbort,"AddFractions:  couldn't factor denominators"));
  330.                 /* since we are multiplying each fraction by N/N, we need to multiply */
  331.                 /* the numerators by the same thing we multiplied the denominators by. */
  332.                 FractionTemp = Left->Fraction * (Right->Denominator / GCF)
  333.                     - Right->Fraction * (Left->Denominator / GCF);
  334.             }
  335.         /* add the integer components */
  336.         IntegerTemp = Left->Integer - Right->Integer;
  337.         /* if there was an overflow in the fractional part, carry it to the integer */
  338.         ERROR(FractionTemp >= DenominatorTemp,
  339.             PRERR(AllowResume,"SubFractions:  overflow occurred when it shouldn't"));
  340.         if (FractionTemp < 0)
  341.             {
  342.                 /* since we are adding, the amount of carry should never be more than 1 */
  343.                 FractionTemp += DenominatorTemp;
  344.                 IntegerTemp -= 1;
  345.             }
  346.         ERROR(FractionTemp < 0,PRERR(ForceAbort,
  347.             "SubFractions:  numerator is way too small"));
  348.         /* store result */
  349.         Dest->Integer = IntegerTemp;
  350.         Dest->Fraction = FractionTemp;
  351.         Dest->Denominator = DenominatorTemp;
  352.     }
  353.